package likou.jindian;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/10 10:30
 */
public class _08_13 {
    public static void main(String[] args) {
    }

    public int pileBox(int[][] box) {
        if (box.length < 1) {
            return 0;
        }
        if (box.length == 1) {
            return box[0][2];
        }

        Arrays.sort(box, (val1, val2) -> {
            int compareVal = Integer.compare(val2[2], val1[2]);
            if (compareVal == 0) {
                compareVal = Integer.compare(val2[0], val1[0]);
                if (compareVal == 0) {
                    return Integer.compare(val2[1], val1[1]);
                }
                return compareVal;
            }
            return compareVal;
        });


        int lastHeight = -1;
        int max = 0;
        for (int[] ints : box) {
            if (ints[2] != lastHeight) {
                lastHeight = ints[2];
                max += lastHeight;
            }
        }
        int[] pointResult = new int[box.length];
        return pileBoxNext(box, -1, max, pointResult);
    }

    private int pileBoxNext(int[][] box, int last, int max, int[] pointResult) {
        int result = 0;
        int lastHeight = last >= 0 ? box[last][2] : 0;

        int next = last;
        while (++next < box.length && box[next][2] == lastHeight);
        int lastMaxId = -1;
        for (int i = next; i < box.length; i++) {
            if (box[i][2] != lastHeight) {
                lastHeight = box[i][2];
                max -= lastHeight;
                lastMaxId = -1;
            }
            if (last >= 0 && (box[last][0] <= box[i][0] || box[last][1] <= box[i][1])) {
                continue;
            }

            if (lastMaxId == -1) {
                lastMaxId = i;
            } else if (box[lastMaxId][1] >= box[i][1]) {
                continue;
            }

            if (result > max + lastHeight) {
                return result;
            }
            if (pointResult[i] <= 0) {
                pointResult[i] = pileBoxNext(box, i, max, pointResult) + lastHeight;
            }
            if (result < pointResult[i]) {
                result = pointResult[i];
            }
        }
        return result;
    }
}
